package com.zk.algorithm.array;

import com.zk.algorithm.annotation.JianZhiOffer;

/**
 * 42. 连续子数组的最大和
 *
 * [1, -2, 3, 10, -4, 7, 2, -5]
 * 结果：[3, 10, -4, 7, 2]
 */
@JianZhiOffer
public class GreatestSumOfSubArray {

    public int findGreatestSumOfSubArray(int[] array) {
        if (array == null) {
            throw new NullPointerException("array can not be empty !");
        }

        int curSum = 0;
        int greatestSum = Integer.MIN_VALUE;

        for (int i = 0; i < array.length; i++) {
            if (curSum <= 0) {
                curSum = array[i];
            } else {
                curSum += array[i];
            }

            if (curSum > greatestSum) {
                greatestSum = curSum;
            }
        }

        return greatestSum;
    }

}
